package pers.tz.题目.排序;

import pers.tz.common.ArrayUtils;

/**
 * @author irony
 * @date 2024-03-16
 */
public class 归并排序 {
    public static void main(String[] args) {
        int[] ints = ArrayUtils.generateRandomArray(10, 1, 15);
        ArrayUtils.printArray(ints);

        mergeSort(ints);
        ArrayUtils.printArray(ints);
    }

    // 双指针 + 辅助数组，时间复杂度O(n * log n)
    private static void mergeSort(int[] ints) {
        if (ints == null || ints.length < 2) {
            return;
        }

        process(ints, 0, ints.length - 1);
    }

    private static void process(int[] ints, int L, int R) {
        if (L == R) {
            return;
        }

        int middle = (L + R) / 2;
        process(ints, L, middle);
        process(ints, middle + 1, R);

        merge(ints, L, middle, R);
    }

    private static void merge(int[] ints, int L, int middle, int R) {
        int p1 = L;
        int p2 = middle + 1;
        int[] ans = new int[R - L + 1];
        int i = 0;

        while (p1 <= middle && p2 <= R) {
            if (ints[p1] <= ints[p2]) {
                ans[i++] = ints[++p1];
            } else {
                ans[i++] = ints[++p2];
            }
        }

        while (p1 <= middle) {
            ans[i++] = ints[p1++];
        }
        while (p2 <= R) {
            ans[i++] = ints[p2++];
        }

        System.arraycopy(ans, 0, ints, 0, ans.length);
    }
}
